package site.wanjiahao.heap;

import java.util.Collection;
import java.util.Comparator;

public class MinHeap<E> extends AbstractHeap<E> {

    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;

    public MinHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);
        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            // 数组深拷贝
            size = elements.length;
            int len = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[len];
            System.arraycopy(elements, 0, this.elements, 0, size);
            // 批量舰堆
            heapify();
        }
    }

    public MinHeap(Collection<E> collection, Comparator<E> comparator) {
        super(comparator);
        if (collection == null || collection.size() == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            // 数组深拷贝
            size = collection.size();
            int len = Math.max(size, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[len];
            int i = 0;
            for (E e : collection) {
                this.elements[i++] = e;
            }
            // 批量舰堆
            heapify();
        }
    }

    public MinHeap(E[] elements) {
        this(elements, null);
    }

    public MinHeap() {
        this((E[]) null, null);
    }

    public MinHeap(Comparator<E> comparator) {
        this((E[]) null, comparator);
    }

    @Override
    public void add(E ele) {
        checkNullEle(ele);
        ensureCapacity();
        // 直接添加末尾
        elements[size] = ele;
        // 上滤操作
        siftUp(size++);
    }

    @Override
    public void addAll(Collection<E> collection) {
        if (collection == null && collection.size() == 0) return;
        for (E e : collection) {
            add(e);
        }
    }

    @Override
    public E get() {
        checkEmpty();
        return elements[0];
    }

    @Override
    public E remove() {
        checkEmpty();
        // --size size-- 相当于 size = size - 1, 会对size的值重新赋值
        int index = --size;
        E old = elements[0];
        elements[0] = elements[index];
        elements[index] = null;
        siftDown(0);
        return old;
    }

    @Override
    public E replace(E ele) {
        checkEmpty();
        E old = elements[0];
        elements[0] = ele;
        siftDown(0);
        return old;
    }

    @Override
    public void clear() {
        if (size != 0) {
            for (int i = 0; i < size; i++) {
                elements[i] = null;
            }
            size = 0;
        }

    }

    private void heapify() {
        // 如果是叶子节点，就没必要下滤。
        // 自下而上的下滤(O(n)) 自上而下的上滤，相当于添加(O(nlogn))
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    // 上滤
    private void siftUp(int index) {
        E cur = elements[index];
        int pIndex;
        boolean swap = false;
        while ((pIndex = (index - 1) >> 1) >= 0) {
            if (compare(elements[pIndex], cur) < 0) break;
            // 交换数据
            elements[index] = elements[pIndex];
            index = pIndex;
            swap = true;
        }
        if (swap) elements[index] = cur;
    }

    // 下滤
    private void siftDown(int index) {
        E cur = elements[index];
        int cIndex;
        boolean swap = false;
        while ((cIndex = (index << 1) + 1) < size) {
            int rIndex = cIndex + 1;
            // 找出左右节点最大值
            if (rIndex < size) {
                // 存在右节点
                cIndex = compare(elements[rIndex], elements[cIndex]) > 0? cIndex: rIndex;
            }
            if (compare(elements[cIndex], cur) > 0) break;
            // 交换元素
            elements[index] = elements[cIndex];
            index = cIndex;
            swap = true;
        }
        if (swap) elements[index] = cur;
    }

    // 扩容
    private void ensureCapacity() {
        if (size < elements.length) return;
        // 扩容
        E[] newAry = (E[]) new Object[elements.length << 1];
        System.arraycopy(elements, 0, newAry, 0, elements.length);
        elements = newAry;
    }

    private void checkEmpty() {
        if (size == 0) throw new RuntimeException("Heap is empty !");
    }

    private void checkNullEle(E ele) {
        if (ele == null) throw new IllegalArgumentException("Element is must not null");
    }

    // 比较逻辑
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }

}
